package com.algorithm.pack;

public class ZeroOnePack {

    /**
     * 0-1背包问题
     * @param weight    物品重量数组
     * @param value     物品价值数组
     * @param volume    背包容积
     */
    public static int[][] zeroOnePack(int[] weight,int[] value,int volume){
        int N = weight.length;//物品数

        //F[i][v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值
        int F[][] = new int[N+1][volume+1];

        for(int i=1;i<=N;i++){
            for(int w=weight[i-1];w<=volume;w++){
                //第i件物品的重量为weight[i-1]价值为value[i-1]
                F[i][w] = Math.max(F[i-1][w],value[i-1]+F[i-1][w-weight[i-1]]);
            }
        }

        return F;
    }

    public static int[] zeroOnePack_space(int[] weight,int[] value,int volume){
        int N = weight.length;
        int F[] = new int[volume+1];
        for(int i=1;i<=N;i++){
            for(int w=volume;w>=weight[i-1];w--){
                //F[w]=F[i-1][w]
                //F[w-weight[i-1]]=F[i-1][w-weight[i-1]]
                F[w] = Math.max(F[w],value[i-1]+F[w-weight[i-1]]);
            }
        }

        return F;
    }

    public static int zeroOnePack_recursive(int N,int[] weight,int[] value,int volume){
        if(N==0 || volume==0){
            return 0;
        }

        int i = N-1;
        if(weight[i] > volume){
            return zeroOnePack_recursive(N-1,weight,value,volume);
        }else{
            int value1 = zeroOnePack_recursive(N-1,weight,value,volume);
            int value2 = value[i] + zeroOnePack_recursive(N-1,weight,value,volume-weight[i]);
            return Math.max(value1,value2);
        }
    }
}
